HW#3 --- last modified March 02 2019 21:31:19..

Solution set.

Due date: Oct 23

Files to be submitted:
  Hw3.zip

Purpose: To learn about the relationships betweeen complexity classes, time hierarchy theorems, reductions and completeness.

Related Course Outcomes:

Problem (1) further fleshes out parts of learning outcome (2) [Give a minimal classification of the complexity of a computational problem as being in one of the class ALogTime, L, P, NP, coNP, some level of the polynomial hierarchy, PSPACE, E, EXPTIME, decidable, undecidable] not covered by HW2.

Problem (2) is related to learning outcome (5) [Know conditions under which various of these hierarchies might collapse]. Namely, you will show a collapse which cannot happen.

Problem (3) is directed toward learning outcome (3) [ Show the completeness of a complete problem for each of these classes]

In order to understand completeness you must also understand reductions, so the coding problem is also directed towards learning outcome (3).

Specification:

Submit the following word problems in the file Hw3.tex:

1. Use the time and space hierarchy theorems to give an explicit language: (a) which is decidable but not in EXPTIME, (b) which is in EXPTIME but not in E, (c) which is in E but not in P, (d) which is in PSPACE but not in L.

2. Fix k >0. Show NP≠ SPACE(n^k).

3. For each of the following classes come up with a variation on the halting problem which is complete for that class under logspace reductions: (a) NL, (b) P, (c) NP, (d) PSPACE.

For the coding part of the homework I want you first to write ThreeSAT.java, a program which checks if a collection of 3SAT clauses is satisfiable. This program can do a brute force check of all truth assignments. Your program will be run from the command line with a line like:

java ThreeSAT instance.txt

Here instance.txt is the name of some file containing a 3SAT instance. The format of of this file consists on a sequence of lines with at most 3integers/line. For example,

3 -5 4

would represent the clause with the literals x₃, the negation of x₅, and x₄.

Besides ThreeSAT.java, I would like you to write a program Circuit3CNF.java which should be run from the command line with a line like:

java Circuit3CNF circuit_file.txt

Here circuit_file.txt is a file containing the description of an AND, OR, NOT circuit. Your program should read the file and output a 3CNF formula, in the one line/clause format used above, which is satisfiable iff the original circuit was satisfiable. The file circuit_file.txt consists of a sequence of rows of one of the following four types:

(1) A variable row, this consists of just a nonnegative integer on a line:

23

represents the variable x₂₃.

(2) A not row, which computes the negation of some earlier row. For example:

-15

this row computes the negations of the output of line 15 in this file. It is assumes that a line like this would occur in the 16 or higher line in the file.

(3) An AND Row, which computes the logical AND of two earlier rows. For example:

* 5 27

would compute the logical AND of the values output by line 5 and line 27 in this file. This line would occur at the earliest at line 28 in the file.

(4) An OR Row, which computes the logical OR of two earlier rows. For example:

+ 5 27

would compute the logical AND of the values output by line 5 and line 27 in this file. This line would occur at the earliest at line 28 in the file.

Point Breakdown